package com.tgy.programmer_code_interview_guide._03_binarytree;

import com.tgy.leetcode.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

public class _24_统计完全二叉树节点个数 {

    public static int numOfNode01(TreeNode root) {

        if (root == null) {

            return 0;
        }

        Queue<TreeNode> queue = new LinkedList<>();

        int twoDegreeCount = 0;
        boolean flag = false;
        queue.offer(root);
        TreeNode node;
        while (!queue.isEmpty()) {

            node = queue.poll();

            if (node.right == null) {

                if (node.left !=null) {

                    flag = true;
                }

                break;
            }
            twoDegreeCount++;
            queue.offer(node.left);
            queue.offer(node.right);

        }

        int sum  = twoDegreeCount + twoDegreeCount + 1;

        if (flag) {
            sum++;
        }

        return sum;
    }

    public static int numOfNode(TreeNode root) {

        int allLevel = allLevel(root);

        if (allLevel <= 1) {

            return allLevel;
        }

        return doNumOfNode(root,allLevel,1);
    }

    private static int doNumOfNode(TreeNode node, int allLevel, int level) {


        if (node == null) {
            return 0;
        }

        int rightLevel = allLevel(node.right);

        if (allLevel == (rightLevel + level)) {
            return (int) (Math.pow(2,rightLevel)) + doNumOfNode(node.right,allLevel,level + 1);
        }else {
            return (int) (Math.pow(2,rightLevel)) + doNumOfNode(node.left, allLevel, level + 1);
        }

    }

    private static int allLevel(TreeNode root) {

        int level = 0;

        TreeNode node = root;
        while (node != null) {

            level++;
            node = node.left;
        }

        return level;
    }

    public static void main(String[] args) {


        /**
         *                  6
         *
         *              3        8
         *
         *          1       4   9    10
         *
         *
         *                  6
         *
         *              3        8
         *
         *          1       4
         */
        TreeNode t1 = new TreeNode(6);
        t1.left = new TreeNode(3);
//        t1.left.left = new TreeNode(1);
//        t1.left.right = new TreeNode(4);
        t1.right = new TreeNode(8);
//        t1.right.left = new TreeNode(9);
//        t1.right.right = new TreeNode(10);

        System.out.println(numOfNode(t1));

    }
}
